λ¬Έμ
μ μ¬μκ°μ λλμ΄ λ€μ΄, μΌλΆ νμμ΄ μ²΄μ‘볡μ λλλΉνμ΅λλ€. λ€νν μ¬λ² 체μ‘λ³΅μ΄ μλ νμμ΄ μ΄λ€μκ² μ²΄μ‘볡μ λΉλ €μ£Όλ € ν©λλ€. νμλ€μ λ²νΈλ 체격 μμΌλ‘ λ§€κ²¨μ Έ μμ΄, λ°λ‘ μλ²νΈμ νμμ΄λ λ°λ‘ λ·λ²νΈμ νμμκ²λ§ 체μ‘볡μ λΉλ €μ€ μ μμ΅λλ€. μλ₯Ό λ€μ΄, 4λ² νμμ 3λ² νμμ΄λ 5λ² νμμκ²λ§ 체μ‘볡μ λΉλ €μ€ μ μμ΅λλ€. 체μ‘λ³΅μ΄ μμΌλ©΄ μμ μ λ€μ μ μκΈ° λλ¬Έμ 체μ‘볡μ μ μ ν λΉλ € μ΅λν λ§μ νμμ΄ μ²΄μ‘μμ μ λ€μ΄μΌ ν©λλ€.
μ 체 νμμ μ n, 체μ‘볡μ λλλΉν νμλ€μ λ²νΈκ° λ΄κΈ΄ λ°°μ΄ lost, μ¬λ²μ 체μ‘볡μ κ°μ Έμ¨ νμλ€μ λ²νΈκ° λ΄κΈ΄ λ°°μ΄ reserveκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, 체μ‘μμ μ λ€μ μ μλ νμμ μ΅λκ°μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
μ νμ¬ν
- μ 체 νμμ μλ 2λͺ μ΄μ 30λͺ μ΄νμ λλ€.
- 체μ‘볡μ λλλΉν νμμ μλ 1λͺ μ΄μ nλͺ μ΄νμ΄κ³ μ€λ³΅λλ λ²νΈλ μμ΅λλ€.
- μ¬λ²μ 체μ‘볡μ κ°μ Έμ¨ νμμ μλ 1λͺ μ΄μ nλͺ μ΄νμ΄κ³ μ€λ³΅λλ λ²νΈλ μμ΅λλ€.
- μ¬λ² 체μ‘λ³΅μ΄ μλ νμλ§ λ€λ₯Έ νμμκ² μ²΄μ‘볡μ λΉλ €μ€ μ μμ΅λλ€.
- μ¬λ² 체μ‘볡μ κ°μ Έμ¨ νμμ΄ μ²΄μ‘볡μ λλλΉνμ μ μμ΅λλ€. μ΄λ μ΄ νμμ 체μ‘볡μ νλλ§ λλλΉνλ€κ³ κ°μ νλ©°, λ¨μ 체μ‘λ³΅μ΄ νλμ΄κΈ°μ λ€λ₯Έ νμμκ²λ 체μ‘볡μ λΉλ €μ€ μ μμ΅λλ€.
μ μΆλ ₯ μ
| n | lost | reserve | return |
|---|---|---|---|
| 5 | [2, 4] | [1, 3, 5] | 5 |
| 5 | [2, 4] | [3] | 4 |
| 3 | [3] | [1] | 2 |
π Logic
for (int l : lost) {
if (map.containsKey(l)) map.computeIfPresent(l, (k, v) -> v - 1);
else lostMap.put(l, 0);
}
for (int l : lostMap.keySet()) {
if (map.containsKey(l - 1) && map.get(l - 1) > 0) {
map.computeIfPresent(l - 1, (k, v) -> v - 1);
map.put(l, 0);
} else if (map.containsKey(l + 1) && map.get(l + 1) > 0) {
map.computeIfPresent(l + 1, (k, v) -> v - 1);
map.put(l, 0);
} else map.put(l, -1);
}
-
νμκ³Ό 체μ‘볡 κ°μ μ 보λ₯Ό
MapμΌλ‘ μ μ₯νλ€.reserveμ μλ νμλ€μ λͺ¨λ 체μ‘볡 μλ₯Ό 1κ°λ‘ μ§μ νλ€.
- λ¨Όμ
lostμreserveλ λ€μ μλ νμμ κ²½μ°λ μκΈ° 체μ‘볡μ μκΈ°κ° μ¨μΌ νλ―λ‘, 체μ‘볡μ λλλΉν νμ λͺ©λ‘μΈlostMapμ λ£μ§ μκ³ , ν΄λΉ νμμ 체μ‘볡 μλ 0μΌλ‘ updateνλ€. -
lostMapμλ μ΄μ 체μ‘볡μ λΉλ €μΌ νλ νμλ€λ§ μ‘΄μ¬νλ€.- μ λ²νΈμ νμλ€μκ² λΉλ¦΄ μ μλμ§ νμΈνκ³ , 체μ‘볡 κ°μ μ 보λ₯Ό μμ νλ€.
- μ΅μ’ μ μΌλ‘ 체μ‘볡 κ°μκ° 0 μ΄μμΈ νμλ€μ μλ₯Ό μΌλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Solution {
int[] possible;
public int solution(int n, int[] lost, int[] reserve) {
Arrays.sort(lost);
Arrays.sort(reserve);
Map<Integer, Integer> map = new HashMap<>();
Map<Integer, Integer> lostMap = new HashMap<>();
for (int r : reserve)
map.put(r, 1);
for (int l : lost) {
if (map.containsKey(l)) map.computeIfPresent(l, (k, v) -> v - 1);
else lostMap.put(l, 0);
}
for (int l : lostMap.keySet()) {
if (map.containsKey(l - 1) && map.get(l - 1) > 0) {
map.computeIfPresent(l - 1, (k, v) -> v - 1);
map.put(l, 0);
} else if (map.containsKey(l + 1) && map.get(l + 1) > 0) {
map.computeIfPresent(l + 1, (k, v) -> v - 1);
map.put(l, 0);
} else map.put(l, -1);
}
int answer = 0;
for (int i = 1; i <= n; i++) {
if (map.containsKey(i) && map.get(i) < 0) continue;
answer++;
}
return answer;
}
}
βοΈ Review
- 그리λλ μ΄ν΄λ μλκ³ , μ½λλ μ μ΄μ κ² κ°λ€.
- μ‘΄μ¬ μ¬λΆλ₯Ό νμΈνκΈ° μν
Mapμ μ μ©ν κ² κ°λ€.
π μΆμ²
Programmers : https://programmers.co.kr/learn/courses/30/lessons/42862